package com.example.jianzhioffer;

import java.util.Stack;

/**
 * Created by Quincy on 2018/9/15.
 * 操作给定的二叉树，将其变换为源二叉树的镜像。
 * 二叉树的镜像定义：源二叉树
      8
    /  \
   6   10
  / \  / \
 5  7 9 11
 镜像二叉树
      8
    /  \
  10   6
  / \  / \
 11 9 7  5
 */
public class MinorTree {
    class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 递归
     * 思路1：如果当前节点为空，返回，否则交换该节点的左右节点，递归的对其左右节点进行交换处理。
     * */
    public static void mirrorTree1(TreeNode root){
        if(root==null)
            return;
        //交换该节点指向的左右节点。
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        //对其左右孩子进行镜像处理。
        mirrorTree1(root.left);

        mirrorTree1(root.right);
    }

    /**
     * 非递归
     * 先序遍历，如果根节点不为 null 将根节点入栈，当栈不为 null 出栈，交换左右节点，如果左右节点不为 null 入栈。
     * */
    public static void mirrorTree2(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        if (root != null)stack.push(root);
        while (!stack.isEmpty()){
            //当栈不为 null 时出栈，交换左右子树。
            TreeNode root1 = stack.pop();
            swap(root1);
            if (root1.right != null){
                stack.push(root1.right);
            }
            if (root1.left != null){
                stack.push(root1.right);
            }

        }
    }

    public static void swap(TreeNode root)
    {
        TreeNode temp;
        temp=root.right;
        root.right=root.left;
        root.left=temp;
    }
}
